package com.cn.algorithm01;

/**
 *搜索二叉树：任何一个子树的左比中小，右比中大。用代码检测是否是搜索二叉树
 * 有效 二叉搜索树定义如下：
 *节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 */
public class Code24_IsSearchTree2 {
    // 创建一个二叉树节点对象
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 判断是否为搜索二叉树
    public boolean isValidBST(TreeNode root) {

        return isBalanced(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public static boolean isBalanced(TreeNode x, long lower, long upper) {
        if (x == null) {
            return true;
        }

        if (x.val <= lower || x.val >= upper) {
            return false;
        }

        return isBalanced(x.left, lower, x.val) && isBalanced(x.right, x.val, upper);
    }

}
